/*
 * Copyright (C), 2015-2018
 * FileName: Solution234
 * Author:   zhao
 * Date:     2018/9/27 10:51
 * Description: 234. 回文链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredthree;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈234. 回文链表〉
 *
 * @author zhao
 * @date 2018/9/27 10:51
 * @since 1.0.1
 */
public class Solution234 {

  /**************************************
   * 题目

   请判断一个链表是否为回文链表。

   示例 1:

   输入: 1->2
   输出: false
   示例 2:

   输入: 1->2->2->1
   输出: true
   进阶：
   你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
   **************************************/

  /**************************************
   *
   * 想法：
   *    一、扔到数组里面，就可以直接判断。空间复杂度有问题O(n)
   *    二、栈。把前半部分扔到栈里面。空间复杂度问题O(n)
   *    三、翻转后半个链表
   *        1. 找到中间位置
   *        2. 翻转后半个数组
   *        3. 循环判断
   *
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *
   * ***********************************/
  public boolean isPalindrome(ListNode head) {
    // 空链表和长度1的链表返回true
    if (head == null || head.next == null) {
      return true;
    }

    ListNode next = head;
    ListNode doubleNext = head;

    // 找到中间位置
    while (doubleNext.next != null && doubleNext.next.next != null) {
      next = next.next;
      doubleNext = doubleNext.next.next;
    }

    // 翻转后半部分的数组
    ListNode cur = next;
    ListNode pre = null;
    while (cur != null) {
      ListNode tmp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = tmp;
    }
    next = pre;

    // 循环判断
    doubleNext = head;
    while (next != null && doubleNext != null) {
      if (doubleNext.val != next.val) {
        return false;
      }
      next = next.next;
      doubleNext = doubleNext.next;
    }

    return true;

  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public void better() {
  }

}
